//
// Created by jizhe hu on 2024/2/20.
//

#ifndef LEETCODE_GREEDY_H
#define LEETCODE_GREEDY_H

#include <vector>
#include <cmath>
#include <set>

using namespace std;

//! 455. 分发饼干
int findContentChildren(vector<int>& g, vector<int>& s) {
    std::sort(g.begin(), g.end());
    std::sort(s.begin(), s.end());

    int i = 0, j = 0, count = 0;
    while (i < g.size() && j < s.size()) {
        if(s[j] >= g[i]) {
            i++;
            j++;
            count++;
        } else {
            j++;
        }
    }

    return count;
}

//! 376. 摆动序列
int wiggleMaxLength(vector<int>& nums) {

}

//! 738. 单调递增的数字
int monotoneIncreasingDigits(int n) {
    int len = 1;
    while(pow(10, len) <= n) {
        len++;
    }
    vector<int> res;
    int i = len - 1;
    for(; i>=0; i--) {
        res.push_back((n / pow(10, i)));
        n -= res.back() * pow(10, i);
    }
    i = 1;
    bool flag = true;
    for(; i<res.size(); i++) {
        if(res[i] < res[i - 1]) {
            while(i >= 1 && res[i] < res[i - 1]) {
                res[i-1]--;
                i--;
            }
            flag = false;
        }
        if(!flag) break;
    }
    i++;
    for(; i<res.size(); i++) {
        res[i] = 9;
    }
    int sum = 0;
    for(i = 0, len = res.size() - 1; i<res.size(); i++, len--) {
        sum += pow(10 , len) * res[i];
    }
    return sum;
}

//! 56. 合并区间
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    function<bool(vector<int>, vector<int>)> cmp = [](vector<int> v1,  vector<int> v2){
        return v1[0] < v2[0];
    };
    sort(intervals.begin(), intervals.end(), cmp);
    vector<vector<int>> res;
    vector<int> tmp = intervals[0];
    int i = 1;
    while(i < intervals.size()) {
        if(tmp[1] >= intervals[i][0]) {
            tmp[1] = max(intervals[i][1], tmp[1]);
            i++;
            continue;
        } else {
            res.push_back(tmp);
            tmp = intervals[i];
            i++;
        }
    }
    res.push_back(tmp);
    return res;
}

//! 435. 无重叠区间
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    function<bool(vector<int>, vector<int>)> cmp = [](vector<int> v1,  vector<int> v2){
        return v1[0] < v2[0];
    };
    sort(intervals.begin(), intervals.end(), cmp);
}

//! 122. 买卖股票的最佳时机 II
int maxProfit(vector<int>& prices) {
    int res = 0;
    for(int i=1; i < prices.size(); i++) {
        res += max(0, prices[i] - prices[i - 1]);
    }
    return res;
}

//! 53. 最大子数组和
int maxSubArray(vector<int>& nums) {
    int res = INT_MIN;
    int cur_res = 0;
    for(int i=0; i<nums.size(); i++) {
        cur_res += nums[i];
        if(cur_res < 0) cur_res = 0;
        res = max(res, cur_res);
    }
    return res;
}

//! 860. 柠檬水找零
bool lemonadeChange(vector<int>& bills) {
    vector<int> changes(3);
    for(int i=0; i<bills.size(); i++) {
        if(bills[i] == 5) changes[0]++;
        if(bills[i] == 10) {
            changes[0]--;
            if(changes[0] < 0) return false;
            changes[1]++;
        }
        if(bills[i] == 20) {
            if(changes[1] > 0) {
                changes[1]--;
                changes[0]--;
            } else {
                changes[0] -= 3;
            }
            if(changes[0] < 0) return false;
        }
    }
    return true;
}

//! 452. 用最少数量的箭引爆气球
int findMinArrowShots(vector<vector<int>>& points) {
    function<bool(vector<int>, vector<int>)> cmp = [](vector<int> v1,  vector<int> v2){
        return v1[0] < v2[0];
    };
    sort(points.begin(), points.end(), cmp);
    int res = 1;
    int cur_end = points[0][1];
    for (int i=1; i<points.size(); i++) {
        if(points[i][0] <= cur_end) {
            cur_end = min(cur_end, points[i][1]);
        } else {
            res++;
            cur_end = points[i][1];
        }
    }
    return res;
}

//! 763. 划分字母区间
vector<int> partitionLabels(string s) {
    set<char> cur_set;
    vector<int> res;
    int start , end;
    int i = 0;
    while(i < s.size()) {
        for(end = s.size() - 1; end>=0; end--) {
            if(s[end] == s[i]) break;
        }
        cur_set.insert(s[i]);
        start = i;
        while(i <= end) {
            if(cur_set.find(s[i]) == cur_set.end()) {
                cur_set.insert(s[i]);
                int cur_end;
                for(cur_end = s.size() - 1; cur_end>=i; cur_end--) {
                    if(s[cur_end] == s[i]) break;
                }
                end = max(end, cur_end);
            }
            i++;
        }
        res.push_back(end - start + 1);
        cur_set.clear();
    }
    return res;
}

//! 55. 跳跃游戏
bool canJump_(vector<int>& nums) {
    vector<int> targets;
    for(int i=0; i<nums.size(); i++) {
        targets.push_back(i + nums[i]);
    }
    function<bool(int)> func = [&targets, &func](int target){
        int next_target;
        for(next_target=0; next_target<target; next_target++) {
            if(targets[next_target] >= target) break;
        }
        if(next_target == 0) return true;
        if(next_target == target) return false;
        return func(next_target);
    };
    return func(nums.size() - 1);
}

//! 55. 跳跃游戏
bool canJump(vector<int>& nums) {
    int cover = 0;
    if (nums.size() == 1) return true; // 只有一个元素，就是能达到
    for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
        cover = max(i + nums[i], cover);
        if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
    }
    return false;
}

//! 45. 跳跃游戏II
int jump(vector<int>& nums) {
    vector<int> targets;
    for(int i=0; i<nums.size(); i++) {
        targets.push_back(i + nums[i]);
    }
    int target = nums.size() - 1;
    int i = 0;
    int res = 0;
    while(i < target) {
        if(targets[i] >= target) {
            target = i;
            res++;
            i = 0;
        } else {
            i++;
        }
    }
    return res;
}

//! 406. 根据身高重建队列
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    function<bool(vector<int>, vector<int>)> cmp = [](vector<int> a, vector<int> b){
        if(a[0] < b[0]) {
            return true;
        } else if(a[0] == b[0] && a[1] < b[1]) {
            return true;
        } else {
            return false;
        }
    };
    sort(people.begin(), people.end(), cmp);
    vector<vector<int>> res;

    int end = people.size() - 1;
    while (end >= 0) {
        int cur = people[end][0];
        int start = end;
        while(start > 0 && people[start - 1][0] == cur) start--;
        for(int i=start; i<=end; i++) {
            res.insert(res.begin() + people[i][1], people[i]);
        }
        end = start - 1;
    }

    return res;
}
#endif //LEETCODE_GREEDY_H
